/*
 * TBX: ToolBoX of Simgrid : some convenient tools (FIFO lists, hash
 * tables, graphs,...)  Copyright (C) 2002 "the MSG Team" (see AUTHORS
 * file).
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation; either version 2, or (at
 * your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
 * USA.
 */

#ifndef SG_HASHTABLE_H
#define SG_HASHTABLE_H

/* WARNING:
 *
 * When writing loops with l_getFirstBucket() and
 * l_getNextbucket(), things can go wrong is the body of the
 * loop removes elements from the HashTable. Typically, 
 * remove(l,b), l_getNextBucket(l,b) will NOT work.
 *
 * That's why the function l_copyList() is provided. First, make
 * a copy. cruise through the copy, but remove stuff in the
 * original.
 */

typedef void *TBX_HashTable_Content_t;
typedef const void *TBX_HashTable_Search_t;

/* Bucket structure */
typedef struct TBX_HashTable_Bucket {
  TBX_HashTable_Content_t content;
  int hashcode;
  struct TBX_HashTable_Bucket *next;
} *TBX_HashTable_Bucket_t;

/* Hash table structure */
#define HASH_NB_BUCKETS 2023

typedef struct TBX_HashTable {
  int count;			/* total number of elements */
  /* in the Hash Table. Used  */
  /* only for info purposes   */
  TBX_HashTable_Bucket_t buckets[HASH_NB_BUCKETS];
/*   int next_bucket_index[HASH_NB_BUCKETS]; */
} *TBX_HashTable_t;

/* help functions */
TBX_HashTable_Bucket_t TBX_HashTable_newBucket(void);
void TBX_HashTable_freeBucket(TBX_HashTable_Bucket_t);

/* API */
TBX_HashTable_t TBX_HashTable_newList(void);
void TBX_HashTable_freeList(TBX_HashTable_t,
			    void (*free_content) (void *));
void TBX_HashTable_insert(TBX_HashTable_t, TBX_HashTable_Content_t,
			  int (*)(TBX_HashTable_Content_t));
void TBX_HashTable_remove(TBX_HashTable_t, TBX_HashTable_Content_t,
			  int (*)(TBX_HashTable_Content_t));
int TBX_HashTable_isInList(TBX_HashTable_t, TBX_HashTable_Content_t,
			   int (*)(TBX_HashTable_Content_t));
TBX_HashTable_Content_t *TBX_HashTable_generalsearch(TBX_HashTable_t,
						     TBX_HashTable_Search_t,
						     int (*)
						      (TBX_HashTable_Content_t),
						     int (*)
						      (TBX_HashTable_Content_t,
						       TBX_HashTable_Search_t));
TBX_HashTable_Content_t TBX_HashTable_smartsearch(TBX_HashTable_t,
						  TBX_HashTable_Search_t,
						  int (*)
						   (TBX_HashTable_Content_t,
						    TBX_HashTable_Search_t));
void TBX_HashTable_apply(TBX_HashTable_t,
			 void (*)(TBX_HashTable_Content_t));
void TBX_HashTable_printHashTable(TBX_HashTable_t);
TBX_HashTable_t TBX_HashTable_copyList(TBX_HashTable_t);

/* The two following functions allows to traverse the
 * whole list in a for loop as follows:
 *   for (b=getFirstBucket(l);b;b=getNextBucket((l),b)) {
 *     Content_t content=b->content;
 *   }
 * WARNING: When doing this sort of loop over all elements,
 * it is not advisable to call removeXXX(), since that will
 * free the current bucket, and the call to getNextBucket()
 * will fail !! The way to free the whole list is to
 * call applyToListXXX(l,freeXXX), or to write a different
 * loop that saves the return value of getNextBucket(l,b) before
 * freeing b. 
 */
TBX_HashTable_Bucket_t TBX_HashTable_getFirstBucket(TBX_HashTable_t);
TBX_HashTable_Bucket_t TBX_HashTable_getNextBucket(TBX_HashTable_t,
						   TBX_HashTable_Bucket_t);

/* A convenient hashfunction() */
int TBX_charHash(char *);

int TBX_checkHashTable(TBX_HashTable_t l);

#endif				/* SG_HASHTABHLE_H */
